#!/usr/bin/python3
import sys
import re
import math

def part1():
    print('part 1')
    sequence = [0 if c == 'L' else 1 for c in sys.stdin.readline().strip()]
    sequence_position = 0
    sys.stdin.readline()
    instructions = {}
    for line in sys.stdin:
        instruction = re.findall(r'[A-Z]+', line.strip())
        instructions[instruction[0]] = (instruction[1], instruction[2])
    position = 'AAA'
    steps = 0
    while position != 'ZZZ':
        target = instructions[position][sequence[sequence_position]]
        print(position, 'goes to', target, sequence_position)
        position = target
        sequence_position = (sequence_position + 1) % len(sequence)
        steps += 1
    print(f'took {steps} steps')

def part2():
    print('part 2')
    sequence = [0 if c == 'L' else 1 for c in sys.stdin.readline().strip()]
    sequence_position = 0
    sys.stdin.readline()
    instructions = {}
    positions = []
    for line in sys.stdin:
        instruction = re.findall(r'[0-9A-Z]+', line.strip())
        instructions[instruction[0]] = (instruction[1], instruction[2])
        if 'A' in instruction[0]:
            positions.append(instruction[0])
    steps = []
    lcm = 1
    for position in positions:
        local_steps = 0
        while position[-1] != 'Z':
            target = instructions[position][sequence[sequence_position]]
            print(position, 'goes to', target, sequence_position)
            position = target
            sequence_position = (sequence_position + 1) % len(sequence)
            local_steps += 1
        steps.append(local_steps)
        lcm = math.lcm(lcm, local_steps)
    print(f'took {steps} steps')
    print(f'first meeting point at {lcm} steps')

if sys.argv[1] in '1':
    part1()
else:
    part2()
